package 动态规划;
//https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=308&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D308
import java.util.*;
public class 零一背包{
    public static void main(String[] args){

        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int v = scn.nextInt();
        int[] vArr = new int[n];
        int[] wArr = new int[n];
        for (int i = 0 ; i < n ; i ++){
            vArr[i] = scn.nextInt();
            wArr[i] = scn.nextInt();
        }
        int[] dp1 = new int[v + 1];
        int[] dp2 = new int[v + 1];
        for (int i = 0 ; i < n ; i ++){
            for (int j = v ; j >= vArr[i] ; j--){
                dp1[j] = Math.max(dp1[j] , dp1[j - vArr[i]] + wArr[i]);
            }
        }
        Arrays.fill(dp2 , Integer.MIN_VALUE);
        dp2[0] = 0;
        for (int i = 0 ; i < n ; i ++){
            for (int j = v ; j >= vArr[i] ; j --){
                dp2[j] = Math.max(dp2[j] , dp2[j - vArr[i]] + wArr[i]);
            }
        }
        if (dp2[v] < 0){
            dp2[v] = 0;
        }
        System.out.println(dp1[v]);
        System.out.println(dp2[v]);
    }
}